This invention is related to U.S. Pat. Application Ser. No. 331,788 filed Apr. 3, 1989.
Public key cryptography is described, for example, in the article: Communications of the ACM, vol. 21, No. 2, February 1978, pages 120-126, R. L. Rivest et al: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Briefly, in public key cryptography, a message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by a publicly specified product N, of two large secret prime numbers P and Q. Decryption is similar, except that a different, secret, power d is used, where EQU e.multidot.d=1 (mod (P-1).multidot.(Q-1)). (1a)
For example, the remainder (which is the encoded message) is raised to the power d and divided by N. The remainder from this division is the original message.
A further feature of such a system is that messages can be "signed" using the secretly held decryption key d, and anyone can verify this signature using the publicly revealed encryption key e.
More particularly, if N is the product of two prime numbers P, Q, i.e., if EQU N=P.multidot.Q;
and if e is relatively prime to .PHI.(N), where EQU .PHI.(N)=(P-1).multidot.(Q-1)
is Euler's totient function of N (the number of integers less than N which are relatively prime to N), then, in modulus N arithmetic, a value d can be determined (see for example, the aforementioned article by Rivest et al) which is the multiplicative inverse of e such that EQU e.multidot.d=1 (mod .PHI.(N)).
The value d is commonly referred to as the secret key counterpart of the public key e.
Thus, if EQU X=Y.sup.e (mod N),
then EQU Y=X.sup.d (mod N)
for all values of Y, O.ltoreq.Y&lt;N.
As mentioned above, this knowledge has been employed in the art of cryptography to design various ciphering systems where typically the integers e and N are disclosed to parties of the cryptographic sessions as a public ciphering key and the integer d is held by the party originating the keys as a secret key value.
Users of these techniques may therefore encipher data Y using the public key (e, N) in reasonable knowledge that only the holder of the secret key value d may decipher the data Y.
Similarly the holder of the secret key value d may encipher data X using (d, N) so that any party with knowledge of the public key values (e, N) may determine that only the holder of the secret key value d could have been the source of data X.
These procedures permit users of the technique to encipher sensitive data and also to digitally sign that data to authenticate its source.
The security of such a system depends in part on the difficulty of factoring the publicly specified value N. In order to prevent N from being factored, a value N is formed from the product of two very large prime numbers P and Q. For example, selecting P, Q&gt;2.sup.150 should prevent N from being factored by any presently known method.
The proof of the aforementioned relationships will now be established.
Given that EQU N=P.multidot.Q
and EQU e.multidot.d=1 mod .PHI.(N) (1b)
where both P and Q are prime integers, then EQU .PHI.(N)=.PHI.(P).multidot..PHI.(Q)=(P-1).multidot.(Q-1).
It will be shown that, if EQU X=Y.sup.e (mod N) (2)
then EQU Y=Y.sup.d (mod N). (3)
Note that if (3) is true, then from (2) EQU X=Y.sup.e.multidot.d (mod N)
From (1b), X.sup.e.multidot.d =X.sup.1+K.PHI.(N) (mod N) where K is some integer.
Since P is prime, it is known (Fermat's "little" theorem) that EQU X.sup.P-1 =1 (mod P) for all X, O&lt;X&lt;P.
Therefore since P-1 divides .PHI.(N)=(P-1).multidot.(Q-1) EQU X.sup.1+K.PHI.(N) =X (mod P) for all X, O.ltoreq.X&lt;P. (4)
Similarly, since Q is prime EQU X.sup.1+K.PHI.(N) =X (mod Q) for all X, O.ltoreq.X&lt;Q. (5)
Equations (4) and (5) imply that EQU X.sup.1+K.PHI.(N) =X (mod P.multidot.Q) for all X, O.ltoreq.X&lt;N,
i.e. EQU X=Y.sup.e =X.sup.e.multidot.d =X.sup.1+K.PHI.(N) =X (mod N)
Therefore, if EQU X=Y.sup.e (mod N)
then EQU Y=X.sup.d (mod N)
for all Y, O.ltoreq.Y&lt;N.
Public key cryptography has particular application to "smart" cards employed as credit and other transaction cards. The microprocessor on a smart card enables it to perform the data calculations associated with public key cryptography. Typically, the secret key d,N is embedded in the card by the card issuer and the public key e,N is made available to various authenticators such as merchants' card readers. To authenticate a card, the authenticator encrypts a message with the public key and the card "proves" its authenticity by decrpyting the encrypted message with its private key. In addition, messages sent from the card may be "signed" by encrypting them first with the private key.
Large international transaction card associations may have many card issuing members. Each card issuing member, such as a bank, will desire that its cards be able to prove the authenticity of its membership in the association. This may be achieved, as described above, by the use of a secret key on each card which corresponds to a public key available to authenticators. However, each member may further desire to issue cards with its own personalized secret key which is unknown to other members. This will allow the issuing member to distinguish itself from other members of the association and prevent other members from masquerading as the issuing member. However, the issuing member does not wish to lose its identity as a member of the association. Furthermore, it is desirable to have the personalized secret key be readily usable with the public key but be unknown to the association.